The design process for many integrated circuits (“chips”) typically contains a number of well known sequential operations. Initially, the proposed functionality of a circuit is analyzed by one or more chip designers. These designers then use design capture tools to enter the logical components of the circuit and their interactions. This step involves generating a description of the logic design to be implemented on the circuit chip in an appropriate machine-readable form. One of the commonly used methods for specifying a design is hardware description language (HDL). This language contains specific functions and syntax to allow complex hardware structures to be described in a compact and efficient way. Logic synthesis tools are available to compile the HDL description specifying the design into lower forms of description. The output of these design tools is a logic design database which completely specifies the logical and functional relationships among the components of the design.
The logic design database is then passed as input to a layout tool, which typically includes a placement tool (placer) and a routing tool (router). Placement is the process whereby each component (or design object) of the design is allocated to a physical position on the chip. The aim of the placer is to place connected design objects in close physical proximity to one another. This conserves routing resources on the chip and increases the probability that the desired interconnections will be successfully completed by the router. Additionally, the performance of the circuit may be improved because excess capacitance and resistance caused by long interconnect paths between design objects will slow down the circuit and, in certain cases, delay critical signals and possibly cause functional failures. Placement may take place either manually or automatically, or in combination. If placement is done manually, a chip designer interacts with a placement tool to define the location on the chip where each design object is to be placed. Automatic placement relies on sophisticated algorithms to place the design objects on the chip without the need for human intervention. As circuits get more complex and device geometry becomes sub-micron, it is rapidly becoming extremely difficult for a human chip designer to manage the complexity of the placement and routing operations. For example, modern designs contain tens of thousands of design objects, making the time needed for complete manual placement prohibitive.
After placement is complete, a routing step is performed. The purpose of routing is to connect the pins in each net of a logic design. A net is a collection of pins that must be connected together electrically by the router. A net may have one or more driver pins and one or more load pins. The driver pins on a net are the source of electrical signals that are fed to the load pins through an interconnection path chosen by the router. The position of the pins in any particular net are decided by the placement process. Routing determines exactly the interconnection paths between driver and load pins on a net. The routing problem can be significantly reduced in complexity if a near-optimal placement of the design objects has been achieved.
After placement and routing, it is often necessary to verify that the design functions in ways expected by the designer. This verification may be achieved by simulation. During post-layout verification, the operation of the logic design is examined. After routing, the precise resistances and capacitances of a design's interconnections are known and consequently, post-layout tools have an accurate picture of the actual circuit in the time domain. The post-layout verification of the design validates time-critical areas and detects glitches and other timing errors. After post-layout verification, masks and test patterns are typically generated for use in manufacturing and testing the circuit.
The design tools involved in the CAD flow that are used for verification and transforming an HDL circuit into a routed circuit are commonly implemented in software executing on an engineering workstation.
It can be seen from the above that placement has an important effect on performance and routability. Thus, it is desirable to generate a placement solution that is as optimal as possible.